package java学习.leetcode.editor.cn.链表;
/**
 * @author 刘世锦
 * 2022-10-02 17:36:31	 当前时间
 */
//给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [1], n = 1
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：head = [1,2], n = 1
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 链表中结点的数目为 sz 
// 1 <= sz <= 30 
// 0 <= Node.val <= 100 
// 1 <= n <= sz 
// 
//
// 
//
// 进阶：你能尝试使用一趟扫描实现吗？ 
// Related Topics 链表 双指针 
// 👍 2243 👎 0

public class 删除链表的倒数第N个结点{
	public static void main(String[] args) {
		Solution solution = new 删除链表的倒数第N个结点().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
//	                    ↓
//	              0 1 2 3 4   count = length-n
//	                  s
//	                      f
//输入：head = [-1,1,2,3,4,5], n = 2
//输出：[1,2,3,5]
    public ListNode removeNthFromEnd1(ListNode head, int n) {
    	int count = 0;
    	ListNode virtualNode = new ListNode(-1,head);
    	ListNode cur = virtualNode;
		while (cur.next!=null){
			cur = cur.next;
			count++;
		}
		if (n>count||n<0){
			return null;
		}
		ListNode cur1 = virtualNode;
		for (int i = 0; i < count-n; i++) {
			cur1 = cur1.next;
		}
		cur1.next = cur1.next.next;
		return virtualNode.next;
	}
//	                    ↓
//	              0 1 2 3 4   count = length-n
//	                s
//	                      f
//输入：head = [-1,1,2,3,4,5], n = 2
//输出：[1,2,3,5]
//	快慢指针

	/**
	 * 快慢指针： 1. 先让fast先走n步，
	 * 			 1.1 为确保slow最后走到被删除节点node的前一个节点
	 * 			 	fast再走一步
	 * 			2. slow与fast一起走，直到fast为null，此时开始删除
	 */
	public ListNode removeNthFromEnd(ListNode head, int n) {
			ListNode visualNode = new ListNode(-1,head);
			ListNode fast = visualNode,slow = visualNode;
			while (n>0&&fast.next!=null){
				fast = fast.next;
				n--;
			}
			fast = fast.next;
			while (fast!=null){
				slow = slow.next;
				fast = fast.next;
			}
			slow.next = slow.next.next;
		//    	若 [1],n=1,则返回[],此时返回head就不对了，应该返回 虚拟节点的下一个节点
		return visualNode.next;
	}

}

	class ListNode {
		int val;
		ListNode next;
		ListNode() {}
		ListNode(int val) { this.val = val; }
		ListNode(int val, ListNode next) { this.val = val; this.next = next; }
	}
//leetcode submit region end(Prohibit modification and deletion)

}
